多核计算实验报告
========

实验内容
--------

* 使用Verlet积分(Velocity Verlet)对粒子运动进行数值模拟
* 通过profiler找到程序运行瓶颈
* 利用OpenMP并行化在多核系统上提高性能
* 将程序hotspot部分的代码用OpenCL重新实现来进一步提高性能
* 用OpenGL可视化粒子运动，实时演示

Verlet积分
--------

本实验使用Verlet积分对粒子进行数值模拟。粒子之间的相互作用力由Lennard-Jones势函数[^Lennard-Jones Potential]确定。

Profiling
--------

`verlet.exe`: 22621 ms
Profiling工具使用`gcc`中的`gprof`程序，步骤如下：

1. 首先用`-O0 -pg -fno-inline-small-functions`参数编译可执行文件`verlet.exe`；
2. 运行`verlet.exe`，程序自动在目录下生成`gmon.out`文件，其中包含了profile数据信息；
3. 运行`gprof verlet.exe > gprof.txt`生成报告。

分析结果：

	Each sample counts as 0.01 seconds.
	  %   cumulative   self              self     total           
	 time   seconds   seconds    calls  us/call  us/call  name    
	 55.96     29.51    29.51 319601000     0.09     0.09  distance(double*, double*, double*)
	 43.83     52.62    23.11                             Scene_compute(_Scene*)
	  0.21     52.73     0.11     1000   110.00   110.09  Scene_update(_Scene*, double)
	  0.00     52.73     0.00        1     0.00     0.00  Scene_free(_Scene*)
	  0.00     52.73     0.00        1     0.00     0.00  Scene_new(double, double, double, int)

Call graph:

	granularity: each sample hit covers 4 byte(s) for 0.02% of 52.73 seconds

	index % time    self  children    called     name
	                                                 <spontaneous>
	[1]     99.8   23.11   29.51                 Scene_compute(_Scene*) [1]
	               29.51    0.00 319600000/319601000     distance(double*, double*, double*) [2]
	-----------------------------------------------
	                0.00    0.00    1000/319601000     Scene_update(_Scene*, double) [4]
	               29.51    0.00 319600000/319601000     Scene_compute(_Scene*) [1]
	[2]     56.0   29.51    0.00 319601000         distance(double*, double*, double*) [2]
	-----------------------------------------------
	                                                 <spontaneous>
	[3]      0.2    0.00    0.11                 main [3]
	                0.11    0.00    1000/1000        Scene_update(_Scene*, double) [4]
	                0.00    0.00       1/1           Scene_new(double, double, double, int) [7]
	                0.00    0.00       1/1           Scene_free(_Scene*) [6]
	-----------------------------------------------
	                0.11    0.00    1000/1000        main [3]
	[4]      0.2    0.11    0.00    1000         Scene_update(_Scene*, double) [4]
	                0.00    0.00    1000/319601000     distance(double*, double*, double*) [2]
	-----------------------------------------------
	                0.00    0.00       1/1           main [3]
	[6]      0.0    0.00    0.00       1         Scene_free(_Scene*) [6]
	-----------------------------------------------
	                                   1             Scene_new(double, double, double, int) [7]
	                0.00    0.00       1/1           main [3]
	[7]      0.0    0.00    0.00       1+1       Scene_new(double, double, double, int) [7]
	                                   1             Scene_new(double, double, double, int) [7]
	-----------------------------------------------


显然程序的瓶颈在`distance`和`Scene_compute`函数调用上。

SIMD指令优化
--------

`gcc`可以自动完成SIMD优化。在本实验中，使用`-msse2`或者`-msse3`编译的程序和只用`O2`编译的比较，速度是接近的。

OpenMP并行化
--------

		int i, j, d;
		double dis, scales[3];
		...
	#pragma omp parallel \
		default (shared) private (i, j, d, dis, scales)
	#pragma omp for
		for (i=0; i<scene->nParticles; i++) {
			for (j=i+1; j<scene->nParticles; j++) {
				...
				for (d=0; d<3; d++) {
					...
				}
			}
		}

OpenMP优化后：11085ms
加速比：2.04 （四核CPU）


OpenCL
--------

不会做

代码说明
--------

程序由C99/C++写成，使用MinGW gcc 4.6.2编译器在Windows平台上调试通过。

编译方法：

1. 在命令行输入`mingw32-make verlet.exe`编译单线程模拟程序
2. `mingw32-make verlet_openmp.exe`编译模拟程序的OpenMP版本
3. `mingw32-make verletDemo.exe.exe`编译使用OpenMP加速的OpenGL演示程序


[Lennard-Jones Potential]: http://chemwiki.ucdavis.edu/Physical_Chemistry/Quantum_Mechanics/Intermolecular_Forces/Lennard-Jones_Potential



